package com.chilly.stack;

/**
 * 	222. 完全二叉树的节点个数
 * 给出一个完全二叉树，求出该树的节点个数。
 * <p>
 * 如何使用完全二叉树的特点更快解出此题。
 * <p>
 * Created by Chilly Cui on 2020/11/24.
 */
public class CountCompleteTreeNodes {

    /*static class TreeNode<T> {
        T data;
        TreeNode left;
        TreeNode right;

        public TreeNode(T data) {
            this.data = data;
        }
    }*/

    /*static class Solution {
        int count = 0;

        public int countNodes(TreeNode treeNode) {
            if (treeNode != null) {
                count++;
            }
            if (treeNode.left != null) {
                countNodes(treeNode.left);
            }
            if (treeNode.right != null) {
                countNodes(treeNode.right);
            }
            return count;
        }
    }*/

    /*static class Solution {
        //对于没有约束的二叉树而言，可以很简单地想到使用下面这个递归的解法：
        public int countNodes(TreeNode root) {
            if (root == null) return 0;
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }*/

    //定义一个tree
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int x) {
            this.val = x;
        }
    }
    static class Solution {
        /**
         * 完全二叉树的特点:
         * 完全二叉树的定义：它是一颗空树，或者它的叶子节点只出现在最后两层，若最后一层不满则叶子节点只在最左侧
         */
        public int countNodes(TreeNode root) {
            if (root == null) return 0;
            int left = countLevel(root.left);
            int right = countLevel(root.right);
            if (left == right) { //left == right。这说明，左子树一定是满二叉树
                return countNodes(root.right) + (1 << left);
            } else {//left != right。说明此时最后一层不满，但倒数第二层已经满了，
                return countNodes(root.left) + (1 << right);
            }
        }

        /**
         * 统计树的深度
         */
        public int countLevel(TreeNode root) {
            int level = 0;
            while (root != null) {
                level++;
                root = root.left;
            }
            return level;
        }

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        //root.right.left = new TreeNode(6);

        //System.out.println(root);

        int countNodes = new Solution().countNodes(root);
        System.out.println("完全二叉树节点个数：" + countNodes);

    }
}
